P3977 [TJOI2015]棋盘

你得知道题目下表是从 $0$ 开始编号，那么每个棋子只能控制与它距离不大于 $1$ 的行。

所以只需压当前这一行的状态，令 $dp(i,S)$ 表示前 $i$ 行棋子，第 $i$ 的摆放状态为 $S$ 的方案。

那么有转移：

$dp(i,S)=\sum_{last} dp(i-1,last)$

转移需要保证 $S,last$ 的两行棋子不冲突，这也是本题的难点。

首先可以处理摆放棋子后不能再摆棋子的位置的二进制。（其实就是输入的模板取反。）

• 判断两行是否冲突

1. 找到第一行的所有 '1'

2. 将 '1' 和 $k$ 对齐后，如果第二行和不能再摆棋子的位置有重合部分则不合法。

同理用第二行判断第一行。

• 判断同行是否冲突

直接看成两行按上述方法比较。

注意第 $k$ 位一定为 $1$ ，会误判为重合，直接减去就可以了。

因为转移是一样的，所以可以用矩阵加速这个过程。

可以通过预处理合法的行来降低时间，不过复杂度最坏还是$\mathcal O(({2^{m}})^3 \log n)= \mathcal O(8^m \log n)$

#include <cstdio>
#define uint unsigned int

const int MAXM = 6;

int n , m , p , k , ban[ 3 ];
int Cnt , rS[ ( 1 << MAXM ) + 1 ];

struct Matrix {
	int n , m; uint a[ ( 1 << MAXM ) + 1 ][ ( 1 << MAXM ) + 1 ];

	Matrix operator * ( const Matrix &oth ) const {
		Matrix Ans = {}; Ans.n = n , Ans.m = oth.m;
		for( int i = 1 ; i <= Ans.n ; i ++ )
			for( int j = 1 ; j <= Ans.m ; j ++ )
				for( int k = 1 ; k <= m ; k ++ )
					Ans.a[ i ][ j ] += a[ i ][ k ] * oth.a[ k ][ j ];
		return Ans;
	}
	Matrix Quick_pow( Matrix x , int po ) {
		Matrix Ans = {}; Ans.n = x.n , Ans.m = x.m;
		for( int i = 1 ; i <= x.n ; i ++ ) Ans.a[ i ][ i ] = 1;
		for( ; po ; po >>= 1 , x = x * x )
			if( po & 1 ) Ans = Ans * x;
		return Ans;
	}
}St , Trans , Ed;

bool check1( int S ) {
	for( int i = 0 ; i < m ; i ++ )
		if( ( S >> i ) & 1 ) {
			if( i == k && ( S & ban[ 1 ] ^ ( 1 << k ) ) ) return 0;
			if( i < k && ( ( S << ( k - i ) ) & ban[ 1 ] ^ ( 1 << k ) ) ) return 0;
			if( i > k && ( ( S >> ( i - k ) ) & ban[ 1 ] ^ ( 1 << k ) ) ) return 0;
		}
	return 1;
}

bool check2( int S1 , int S2 ) {
	for( int i = 0 ; i < m ; i ++ )
		if( ( S1 >> i ) & 1 ) {
			if( i <= k && ( ( S2 << ( k - i ) ) & ban[ 2 ] ) ) return 0;
			if( i > k  && ( ( S2 >> ( i - k ) ) & ban[ 2 ] ) ) return 0;
		}
	for( int i = 0 ; i < m ; i ++ )
		if( ( S2 >> i ) & 1 ) {
			if( i <= k && ( ( S1 << ( k - i ) ) & ban[ 0 ] ) ) return 0;
			if( i > k  && ( ( S1 >> ( i - k ) ) & ban[ 0 ] ) ) return 0;
		}
	return 1;
}

void InitS( ) {
	for( int S = 0 ; S < 1 << m ; S ++ )
		if( check1( S ) ) rS[ ++ Cnt ] = S;
}

int main( ) {
	scanf("%d %d",&n,&m);
	scanf("%d %d",&p,&k);
	for( int i = 0 , x ; i < 3 ; i ++ )
		for( int j = 0 ; j < p ; j ++ )
			scanf("%d",&x) , ban[ i ] |= ( x << j );

	InitS( );

	St.n = 1 , St.m = Cnt;
	St.a[ 1 ][ 1 ] = 1;

	Trans.n = Trans.m = Cnt;
	for( int i = 1 ; i <= Cnt ; i ++ )
		for( int j = 1 ; j <= Cnt ; j ++ )
			Trans.a[ i ][ j ] = check2( rS[ i ] , rS[ j ] );
	
	Ed = St * Trans.Quick_pow( Trans , n );

	uint Ans = 0;
	for( int dS = 1 ; dS <= Cnt ; dS ++ )
		Ans += Ed.a[ 1 ][ dS ];
	printf("%u\n", Ans );
	return 0;
}